/**
 * @file 98.ValidateBST.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-15
 * 
 * @copyright Copyright (c) 2021
 * 
 * BST入门
 * 98.验证二叉搜索树
 * 700.二叉搜索树中的搜索
 * 530. 二叉搜索树的最小绝对差 == 783.二叉搜索树节点最小距离
 * 501. 二叉搜索树中的众数
 * 235.二叉搜索树的最近公共祖先
 * 236.二叉树的最近公共祖先
 */

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
public:
    // 98.
    long long maxVal = INT64_MIN;
    bool isValidBST(TreeNode *root)
    {
        if (!root) {
            return true;
        }
        bool left = isValidBST(root->left);
        if (maxVal < root->val) {
            maxVal = root->val;
        } else {
            return false;
        }
        bool right = isValidBST(root->right);
        return left && right;
    }
    // 700.
    TreeNode *searchBST(TreeNode *root, int val)
    {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val == val) {
            return root;
        } else if (root->val < val) {
            return searchBST(root->right, val);
        } else {
            return searchBST(root->left, val);
        }
    }

public:
    // 530. 维护当前节点与前一个节点之差
    TreeNode *pre = nullptr;
    int minDis = INT32_MAX;
    int getMinimumDifference(TreeNode *root)
    {
        traversal530(root);
        return minDis;
    }

private:
    void traversal530(TreeNode *root)
    {
        if (root == nullptr) {
            return;
        }
        traversal530(root->left);
        if (pre && root->val - pre->val < minDis) {
            minDis = root->val - pre->val;
        }
        pre = root;
        traversal530(root->right);
    }

public:
    // 501.
    int cnt = 0; // 频次
    int maxCnt = 0;
    TreeNode *pre = nullptr;
    vector<int> res;
    vector<int> findMode(TreeNode *root)
    {
        traversal501(root);
        return res;
    }

private:
    void traversal501(TreeNode *root)
    {
        if (root == nullptr) {
            return;
        }
        traversal501(root->left);
        if (pre && root->val == pre->val) {
            ++cnt;
        } else {
            cnt = 1;
        }
        pre = root; // 判断cnt前
        if (maxCnt == cnt) {
            res.push_back(pre->val);
        } else if (maxCnt < cnt) {
            res.clear();
            maxCnt = cnt;
            res.push_back(root->val);
        }
        traversal501(root->right);
    }

public:
    // 235.
    TreeNode *lowestCommonAncestorBST(TreeNode *root, TreeNode *p, TreeNode *q)
    {
#if 0
        // 对BST来说，pq很容易判断左右
        // pq均存在于BST中，即pq不会为空
        if (root == nullptr) {
            return nullptr;
        }
        // pq均在左或均在右
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestorBST(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestorBST(root->right, p, q);
        } else { // pq一左一右，可不就是root本身
            return root;
        }
#endif
        while (root) {
            if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else {
                return root;
            }
        }
        return nullptr;
    }
    // 236. 普通二叉树
    // 普通二叉树不能像BST那样一次甩掉一半，那就遍历呗，找到一个等于pq的节点
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        // 出口：找到一个节点等于p、q
        if (!root) {
            return nullptr;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) {
            return root;
        }
        if (!left) {
            return right;
        } else {
            return left;
        }
    }
};